/**
 * 要求 arr 是非递减的，或通过 mapFn 映射后是非递减的
 * 如果传入了 mapFn 则对 arr[i] 先执行 mapFn(arr[i]) 再进行比较，包括 target
 * 如果传入了左右边界 left 或 right，应该传入开区间边界
 * @param {T[]} arr 
 * @param {T} target 
 * @param {Record<string, Function | number | undefined>} options 
 * 返回最小的满足 arr[i] >= target 的下标
 * 如果不存在，则返回 arr.length
 * @returns {number}
 */
function lower_bound(arr, target, { mapFn, left = -1, right = arr.length } = {}) {
  const targetVal = typeof mapFn === 'function' ? mapFn(target) : target
  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    const midVal = typeof mapFn === 'function' ? mapFn(arr[mid]) : arr[mid]
    midVal < targetVal ? left = mid : right = mid
  }
  return right
}